This invention relates to apparatus for generating binary pseudo-random numbers by use of the maximum-length shift register sequence (hereinafter simply referred to as M sequence).
The advance recently made in computer technology and various digital devices has encouraged adoption of various types of simulation and measurement based on random numbers. For example, various forms of predictive and statistical calculation, simulation of social and economic models, application and simulation in the field of physics and engineerings concerning nuclear power and nuclear fusion, and generation of test data in inspecting and measuring instruments have found use of random numbers. In these fields of application, the execution of simulation and measurement must be carried out at high speeds. Thus, apparatus capable of generating random numbers at such high speeds are in demand.
In computers, random numbers have heretofore been generated in a subroutine of the so-called software by combining instructions for arithmetic operations (addition, subtraction, multiplication, division, etc.) prepared for a computer. Particularly, a congruent method has been used widely in which division operations are predominant. To generate one random number by this method, execution of at least several instructions including those for data loading in the register, execution of divisions, and storage of the results in memories, for example, is required. Further, the execution of division takes up more than the other arithmetic operations such as addition, subtraction, and multiplication. Thus, this method has failed to generate random numbers at high speeds as generally expected.
In measuring instruments, a method has been prevalent which generates binary pseudo-random numbers by use of the M sequence. However, the conventional M sequence method is based primarily on the use of shift registers and therefore, data is produced essentially on the basis of one bit per one clock.
Heretofore, the generation of binary pseudo-random numbers by the M sequence has been effected as follows.
It is now assumed that a sequence {a.sub.i } of "0" and "1" is derived from an asymptotic equation, EQU a.sub.i =c.sub.1 a.sub.i-1 +c.sub.2 a.sub.i-2 + EQU . . . c.sub.p a.sub.i-p (mod.2) (1)
where the constants c.sub.1, c.sub.2, . . . , c.sub.p-2 and c.sub.p-1 are "0" or "1" and c.sub.p is "1". It is provided, however, that all initial values a.sub.0, a.sub.1, . . . and a.sub.p-1 are not 0 (zero).
Then, the sequence {a.sub.i } constitutes an M sequence having a period of 2.sup.p -1 when the coefficients c.sub.1, c.sub.2, . . . and c.sub.p in equation (1) are selected so that a characteristic polynomial, EQU f(x)=1+c.sub.1 x+c.sub.2 x.sup.2 + EQU . . . +c.sub.p x.sup.p ( 2)
will form a primitive polynomial on a Galois field, GF (2).
Information on Galois fields may be found in, for example, "Error-correcting Code" by W. Wesley Peterson. The expression "primitive polynomial on GF (2)" designates such a nature that x.sup.k-1 is indivisible by f(x) when 0&lt;k&lt;2.sup.p -1 and divisible when k=2.sup.p -1.
The sequence {a.sub.i } derived from equation (1) as described above has heretofore been generated by a p-stage linear feedback shift register. It is known that binary pseudo-random numbers of n bits can be obtained with the above shift register as follows. More particularly, successive n (.ltoreq.p) bits of numbers (0 or 1) are extracted from the M sequence {a.sub.i } and arranged to form binary numbers of n-bits, EQU U.sub.k =a.sub.mk+r+1 a.sub.mk+r+2 EQU . . . a.sub.mk+r+n ( 3)
and this sequence {U.sub.k } is used as binary random numbers, where r is a positive integer and m (.ltoreq.n) is an interval at which n bits are extracted sequentially from the sequence {a.sub.i }. Where m and the period 2.sup.p -1 are primes with respect to each other, the period of the sequence {U.sub.k } is 2.sup.p -1. With the conventional apparatus, however, generation of binary pseudo-random numbers of n bits calls for at least n times (n clocks) of shifting operations. This requirement prevents the generation of random numbers at high speeds.